package top.datacluster.basic.algorithm.leetcode.heap;

import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Set;

/**
 * 面试题 17.09. 第 k 个数
 * 有些数的素因子只有 3，5，7，请设计一个算法找出第 k 个数。注意，不是必须有这些素因子，而是必须不包含其他的素因子。例如，前几个数按顺序应该是 1，3，5，7，9，15，21。
 *
 * 示例 1:
 *
 * 输入: k = 5
 *
 * 输出: 9
 */
public class LeetCodeView17_09 {

    public int getKthMagicNumber(int k) {
        Set<Integer> data = new HashSet<>();
        PriorityQueue<Integer> queue = new PriorityQueue<>();
        long[] result = new long[k];
        int index = 0;
        queue.offer(1);
        while (index < result.length){
            if (!data.contains(queue.peek())){
                queue.offer(queue.peek() * 3);
                queue.offer(queue.peek() * 5);
                queue.offer(queue.peek() * 7);
                data.add(queue.peek());
                result[index] = queue.poll();
                index++;
            }else{
                queue.poll();
            }
        }
        return (int)result[result.length - 1];
    }
}
